package dp;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Discretization points with dynamyc programming
 * 
 * @author pixel
 * 
 */
public class DDP {

    private final int d;
    private final Set<Integer> demensions;

    public DDP(int D, Collection<Integer> demensions) {
	this.d = D;
	this.demensions = new HashSet<Integer>(demensions);
    }

    /**
     * Ordered list of discretizations
     * 
     * @return
     */
    public List<Integer> generatePoints() {
	List<Integer> result = new ArrayList<Integer>();
	int[] c = new int[d + 1];

	for (int j = 0; j <= d; ++j)
	    c[j] = 0;
	for (int di : demensions) {
	    for (int j = di; j <= d; ++j) {
		if (c[j] < (c[j - di] + di)) {
		    c[j] = c[j - di] + di;
		}
	    }
	}
	for (int j = 1; j <= d; ++j) {
	    if (j == c[j]) {
		result.add(j);
	    }
	}
	return result;
    }
}
